The invention lies in the telecommunications field. More specifically, the invention relates to a method for processing data received by a receiver, in which data transmitted in successive frames over a transmission link are received. One frame contains a predefined number of bit positions. The received data are processed by means of a maximum a posteriori probability algorithm using metric increments or a maximum likelihood algorithm, whereby the Viterbi algorithm is used. The metric increments for at least one bit position whose value and/or whose so-called reliability value is correlated from frame to frame are thereby calculated in dependence on a current reliability value determined for that bit position. The reliability value is a measure of the probability that the value of the bit position has a predefined value.
A method of this type is known for a Viterbi algorithm, for example from the article xe2x80x9cSource-Controlled Channel Decodingxe2x80x9d by Joachim Hagenauer in xe2x80x9cIEEE Transactions on Communicationsxe2x80x9d, Volume 43, No. 9, September 1995, pages 2449-2457. Substantial parts of the article are also contained in U.S. Pat. No. 5,511,081 to Hagenauer (German patent DE 42 24 214 C2). In particular, formula (21) in the article specifies the calculation of new metrics Mk(m) from old metrics Mkxe2x88x921(m) and an associated metric increment. The index m thereby denotes a specific path and k defines a specific bit position in a frame. A reliability value L(uk) is used in calculating the metric Mk(m). On pages 2454 and 2455 of the article, the so-called HUK algorithm is suggested for the determination of the reliability value L(uk). The algorithm is thereby based on an empirical model in which the reliability values L(uk) are calculated similar to the so-called points in a German third-party liability insurance for cars. Because of the empirical character, the estimates for the reliability values L(uk) are inaccurate. The metric increments are either added to or multiplied by metrics already calculated.
The maximum a posteriori probability algorithm and the maximum likelihood algorithm are algorithms which compare a data sequence transmitted over the transmission link with reference sequences s, and determine the reference sequence s which, with the greatest probability, belongs to the transmitted data sequence. Maximum a posteriori probability means that reference sequence s is selected for which the probability P (s|y) becomes a maximum. The term y represents the received data sequence. Maximum likelihood means that reference sequence s is selected for which the probability P (y|s) becomes a maximum. The transmission link is, for example, a radio channel, a transmission line or else a storage medium from which data are read.
A multiple receiver which is insensitive to noise and has a number of receiving antennas is disclosed in U.S. Pat. No. 5,202,903 to Okanoue (European patent application EP 0 449 327). The received signals are generated by a single transmitted signal, which passes to the antennas via various transmission paths. Branch metrics for the implementation of a Viterbi algorithm are calculated from the received signals from the individual antennas. Before the algorithm is implemented, the branch metrics calculated in relation to the received signals from the individual antennas are weighted and combined. After the Viterbi algorithm has been implemented, this leads to the generation of a symbol sequence which agrees well with a transmitted symbol sequence on which the transmitted signal is based.
It is accordingly an object of the invention to provide a method and device for source-controlled channel decoding using a Kalman filter, which overcomes the above-mentioned disadvantages of the heretofore-known devices and methods of this general type and which specifies a simple method for determining the reliability values which calculates the current reliability values as far as possible without errors and accurately.
With the foregoing and other objects in view there is provided, in accordance with the invention, a method of processing data received by a receiver, which comprises:
receiving data transmitted in successive frames, each containing a predefined number of bit positions, via a transmission link;
processing the received data with a maximum a posteriori probability algorithm using one of metric increments and a maximum likelihood algorithm;
calculating the metric increments for at least one bit position, whose value and/or whose reliability value is correlated from frame to frame, in dependence from a current reliability value determined for the frame being currently processed, whereby the current reliability value is a measure of a probability that the value of the bit position has a predefined value;
determining the current reliability value by using at least one observed reliability value determined for the bit position from a previously processed frame or from the frame being currently processed; and
determining the current reliability value such that a sum formed over several frames of the deviations of an error-free reliability value for the respective frame and of the reliability value determined for the same frame assumes a minimum.
The invention is based on the consideration that the current reliability values could be determined very accurately with an optimization method. However, the difficulty is that reliability values to be used for the optimization are based on an observation which is subject to errors. The errors can be attributed to disturbances during the transmission of the data over the transmission link and to results from the Viterbi algorithm which are subject to errors. Therefore, in the method according to the invention, the target function defined is the sum of the deviations of an essentially error-free reliability value for a frame and of the reliability value determined for the same frame. In this case, the deviation relates to the magnitude of the difference between the actual, error-free reliability value and the determined reliability value. The target function is minimized by the optimization method, so that the reliability values determined in order to implement the Viterbi algorithm approach the error-free reliability values very closely.
In the method according to the invention, the minimization of the target function can be carried out in spite of unknown error-free reliability values, since, in the optimization method, a mathematical model is used which produces a relationship between the reliability values based on the observations and the error-free reliability values. In addition, so-called a priori information is used in the model, that is to say information which is known before the transmission of the data over the transmission link, such as information relating to the correlation of the data or the correlation of the reliability values in successive frames. In this sense, the data source influences the further processing of the data. If the processing is decoding, for example, then one also speaks of source-controlled channel decoding.
In the case of a Viterbi algorithm without iteration, the reliability value based on the observation is generally available only after a delay of one frame. Accordingly, in order to determine the current reliability value, recourse must be had to an observed reliability value which has been determined for the bit position from a frame that has already been processed. If, on the other hand, a Viterbi algorithm with iteration is carried out, then a reliability value based on an observation for the frame currently being processed is already available in the second iteration step. In this case, this observed reliability value is used to determine the current reliability value.
The method according to the invention supplies better results by comparison with the known HUK algorithm, since it can be used to process severely fluctuating source signals, in which the HUK algorithm is not capable of estimating the reliability values sufficient accurately. In the method according to the invention, the reliability values used when implementing the Viterbi algorithm lie close to the actual reliability values, so that the probability of an error in selecting the path is reduced, since the reliability values used influence the selection of the path. Correct selection of a path leads, for example during decoding, to a correctly decoded bit sequence.
In a development of the invention, the reliability values are calculated in accordance with the following formula:       L    ⁡          (              u        1            )        =      log    ⁢                  P        ⁡                  (                                    u              1                        =                          +              1                                )                            P        ⁡                  (                                    u              1                        +                          -              1                                )                    
The term ul represents the value of the bit position, which can preferably be xe2x80x9c+1xe2x80x9d or xe2x80x9cxe2x88x921xe2x80x9d. For instance, P(ul=+1) is the probability that the value in the bit position l considered is xe2x80x9c+1xe2x80x9d. In a corresponding way, P(ul=xe2x88x921) is the probability that the value in the bit position l is xe2x80x9cxe2x88x921xe2x80x9d.
In accordance with an added feature of the invention, during the optimization calculations are not carried out directly using the reliability values but using auxiliary reliability values, to which the following formula preferably applies:
m(ul)=P(ul=+1)xe2x88x92P(ul=xe2x88x921)
By comparison with the reliability values, the auxiliary reliability values have the advantage that they have a value range between xe2x80x9c+1xe2x80x9d and xe2x80x9cxe2x88x921xe2x80x9d for probabilities p between xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d. By contrast, the reliability values have function values from xe2x80x9cxe2x88x92xe2x80x9d to xe2x80x9c+xe2x80x9d in the function range specified, so that calculations are made more difficult in a restricted numeric region, such as is present in mechanical computers.
The conversion of reliability values to auxiliary reliability values and, respectively, from auxiliary reliability values to reliability values is carried out on the basis of a simple mathematical relationship which, for example, is stored in a memory in the form of tabular values.
By means of a recursive optimization in which the current reliability value or the current auxiliary reliability value is calculated recursively from the reliability value or the auxiliary reliability value for the frame last processed, it is possible for the computing outlay during the optimization to be reduced.
For the purpose of optimization, a so-called Kalman filter is advantageously used, in which the optimization is likewise carried out recursively. A filter of this type is specified, for example, in the article xe2x80x9cLeast-squares estimation: from Gauss to Kalmanxe2x80x9d by H. W. Sorenson, in IEEE Spectrum, Volume 7, pages 63-68, dated July 1970. The mathematical model based on the Kalman filter takes into account the fact that the actual reliability values can be determined only indirectly via the reliability values based on an observation which is subject to errors. In addition, the Kalman filter uses statistical properties of the reliability values and of the transmitted data and follows any rapid change in the values of the transmitted data at a sufficient speed.
The method according to the invention may be used advantageously when there are correlations between bit positions of successive frames. This is the case, for example, in the case of bit positions for more significant bits of parameters in a frame which is transmitted in a mobile radio system in accordance with the GSM standard. In a development of the method of the invention, the correlation in the above-mentioned bit positions is used in order to decode these bit positions.
With the above and other objects in view there is also provided, in accordance with the invention, a device for processing data received by a receiver and, in particular, for implementing the aforementioned method. The aforementioned technical effects therefore also apply to this device.
The device comprises:
a receiving unit for receiving data transmitted via a transmission link in frames comprising a predefined number of bit positions;
a metric increment unit connected to the receiving unit for processing the received data with a maximum a posteriori probability algorithm using one of metric increments and a maximum likelihood algorithm;
a computing unit connected to the metric increment unit for determining, for at least one bit position whose value and/or reliability value is correlated from frame to frame, a current reliability value and outputting the current reliability value to the metric increment unit;
the computing unit, in determining the current reliability value, using at least one observed reliability value which has been determined for the bit position from one of a previously processed frame and a frame currently being processed;
the computing unit, in a first option, determining the reliability value such that a sum formed over several frames of the deviations of an error-free reliability value of a frame and of the reliability value determined for the same frame becomes a minimum;
the computing unit, in a second option, determining the reliability value such that a sum formed over several frames of the deviations of an essentially error-free auxiliary reliability value for the respective frame and an auxiliary reliability value determined for the same frame becomes a minimum, the auxiliary reliability values) being calculated from the reliability values by one of a conversion function and an approximation function.
In accordance with a further aspect of the invention, the above-outlined objects are also satisfied with a method of processing data received by a receiver receiving data in successive frames each containing a predefined number of bit positions over a transmission link, which comprises:
processing the received data with a maximum a posteriori probability algorithm using one of metric increments and a maximum likelihood algorithm;
calculating the metric increments, for at least one bit position whose value and/or reliability value is correlated from frame to frame, from a current reliability value determined for the frame currently being processed, which is a measure of the probability that the value of the bit position has a predefined value;
determining the current reliability value with at least two observed reliability values, or at least two already determined reliability values, which are determined for the bit position from associated frames; and
forming the current reliability value, by averaging the observed reliability values, or from the reliability values already determined.
In this case, the current reliability value is calculated from at least two observed reliability values by averaging. This measure is based on the finding that although the reliability value observed in each case does not coincide with the respective actual reliability value, errors in the observation cancel each other out as a result of the averaging.
In a development of the method with averaging, the latter is carried out only in relation to a predefined number of frames that have already been processed, the predefined number remaining constant over several averagings. As a result of this measure, preferably only the respective last section of the sequence of successive frames is taken into account, in a manner similar to that through a window. Rapid adaptation to changing conditions can thus take place. If the Viterbi algorithm is carried out recursively, the frame currently being processed is also included in the window.
In another development of the method with averaging, the data, for example, processed by the Viterbi algorithm, are used directly as observed reliability values. This measure therefore leads to a very accurate determination of the current reliability values, since the average of the processed data coincides with the auxiliary reliability value and the latter, as already mentioned, is a good approximation to the actual, error-free reliability value itself.
Finally, with the above and other objects in view there is also provided, in accordance with the invention, a device for processing received data, comprising:
a receiving unit for receiving data via a transmission link, whereby the data are transmitted in frames comprising a predefined number of bit positions;
a metric increment unit connected to the receiving unit for processing the received data by a maximum a posteriori probability algorithm using one of metric increments and a maximum likelihood algorithm;
a computing unit connected to the metric increment unit, the computing unit, for at least one bit position whose value and/or reliability value is correlated from frame to frame, determining a current reliability value and outputting the current reliability value to the metric increment unit, whereby the reliability value is a measure of a probability that the bit position has a predefined value; and
the computing unit calculating the current reliability value by averaging at least two observed reliability values, or at least two already determined reliability values, determined for the bit position from associated frames.
Other features which are considered as characteristic for the invention are set forth in the appended claims.
Although the invention is illustrated and described herein as embodied in a method and device for source-controlled channel decoding using a Kalman filter, it is nevertheless not intended to be limited to the details shown, since various modifications and structural changes may be made therein without departing from the spirit of the invention and within the scope and range of equivalents of the claims.
The construction and method of operation of the invention, however, together with additional objects and advantages thereof will be best understood from the following description of specific embodiments when read in connection with the accompanying drawings.